package Offer_53_2;

import java.util.HashMap;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2023/3/31 12:58
 * 剑指 Offer 53 - II. 0～n-1中缺失的数字
 *  使用二分,hash,直接遍历 比较时间复杂度。
 */
public class Solution {
    public int missingNumber(int[] nums) {//二分 最好
        int left = 0;
        int right = nums.length-1;
        int mid = -1;
        while (left<= right){
            mid = left + (right-left)/2;
            if (nums[mid] == mid){
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        return left;
    }
    public int missingNumberHash(int[] nums) {//HashMap 最差
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],i);
        }
        for (int i = 0; i < map.size(); i++) {
            if (!map.containsKey(i)){
                return i;
            }
        }
        return nums.length;
    }
    public int missingNumberDri(int[] nums) {//直接遍历 中等
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]!=i){
                return i;
            }
        }
        return nums.length;
    }
}
